import numpy
from matplotlib import pyplot
data=numpy.loadtxt("./ex0.txt",delimiter="\t")[:,1:]
# 可视化
# pyplot.scatter(data[:,0],data[:,1],s=3)
# pyplot.show()


#回归树的预剪枝限制比较多  1.高度 2.方差变化 3.节点树
def get_best_split(data,slimit,nlimit,weight):
    if numpy.unique(data[:, -1]).shape[0] == 1:
        return None, data[0, -1] # 如果值相同则不用划分，直接返回值
    shape = data.shape
    S = numpy.dot(weight,(data[:,-1]-numpy.average(data[:,-1],weights=weight))**2)  # 计算数据原来的总方差
    bestS = numpy.inf
    spIndex = 0
    spValue = 0
    for i in range(shape[1] - 1):
        for j in range(shape[0]):
            right = data[data[:, i] > data[j, i]]
            left = data[data[:, i] <= data[j, i]]
            right_weight=weight[data[:, i] > data[j, i]]
            left_weight=weight[data[:, i] <= data[j, i]]
            if right.shape[0]==0:
                continue
            newS = numpy.dot(right_weight,(right[:,-1]-numpy.average(right[:,-1],weights=right_weight))**2)/numpy.sum(right_weight) + numpy.dot(left_weight,(left[:,-1]-numpy.average(left[:,-1],weights=left_weight))**2)/numpy.sum(left_weight)
            if newS < bestS:
                bestS = newS
                spIndex = i
                spValue = data[j, i]
    # 划分后的方差变化太小则取消此次划分
    if S - bestS < slimit:#限制划分后前后方差变化
        return None, numpy.average(data[:, -1],weights=weight)
    # # 划分后的数据集数量太小则取消此次划分
    # right = data[data[:, spIndex] > spValue]
    # left = data[data[:, spIndex] <= spValue]#用最好的划分方式进行划分
    # if right.shape[0] < nlimit or left.shape[0] < nlimit:#限制划分后的最小节点数
    #     return None, numpy.average(data[:, -1],weights=weight)
    return spIndex, spValue
#构建最复杂的回归树，则每组数据的最小数据量为1，方差变化界限为0
def regression_tree(data,slimit,nlimit,weight,height):
    spIndex, spValue = get_best_split(data,slimit,nlimit,weight)
    if spIndex is None:
        return spValue
    if height==0:#如果已经达到限制的高度
         return numpy.average(data[:,-1],weights=weight)
    tree = {'spIndex': spIndex, 'spValue': spValue}
    right = data[data[:, spIndex] > spValue]
    left = data[data[:, spIndex] <= spValue]
    right_weight = weight[data[:, spIndex] > spValue]/numpy.sum(weight[data[:, spIndex] > spValue])
    left_weight = weight[data[:, spIndex] <= spValue]/numpy.sum(weight[data[:, spIndex] <= spValue])
    tree['right'] = regression_tree(right,slimit,nlimit,right_weight,height-1)
    tree['left'] = regression_tree(left,slimit,nlimit,left_weight,height-1)
    return tree
#对数据进行预测
def predict(tree,X):
    if not isinstance(tree,dict):
        return tree
    if X[tree['spIndex']]<=tree['spValue']:
        return predict(tree['left'],X)
    else:
        return predict(tree['right'],X)
def get_Error(tree,data):
    res=numpy.empty((data.shape[0],))
    for i in range(data.shape[0]):
        res[i]=predict(tree,data[i,:-1])
    return res,(res-data[:,-1])**2/numpy.max(numpy.abs(res-data[:,-1]))**2#使用均方误差作为损失

#实现adaboost.R2算法
height=1
epoch=1000
m,n=data.shape
weight=numpy.ones(m)*100
aggregate_predict=numpy.empty((epoch,m))
aggregate_beta=numpy.empty(epoch)
weak_learners=[]
for i in range(epoch):
    p=weight/numpy.sum(weight)
    tree=regression_tree(data,0.001,1,p,height)
    #计算错误率
    res,L=get_Error(tree,data)
    Error=numpy.dot(p,L)
    if Error>0.5 or Error==0:#错误率>0.5或者等于0时停止
        break
    beta=Error/(1-Error)
    aggregate_predict[i, :] = res
    aggregate_beta[i] = numpy.log(1 / beta)
    tree["confidence"] = aggregate_beta[i]
    # 在beta和预测值的基础上计算新的weight
    weight = weight * beta ** (1-L)  # 注意权重更新时的不同
    # 计算综合结果
    index=numpy.argsort(aggregate_predict[0:i+1,:],axis=0)
    sort_aggregate_predict=numpy.take_along_axis(aggregate_predict[0:i+1,:],index,axis=0)
    sort_aggregate_beta=aggregate_beta[0:i+1][index]
    #取得加权中位数
    fres=sort_aggregate_predict[numpy.sum(numpy.cumsum(sort_aggregate_beta,axis=0)<0.5*sort_aggregate_beta.sum(axis=0),axis=0),numpy.arange(m)]#取得索引
    fErrror=numpy.sum((fres-data[:,-1])**2)
    print(fErrror,Error)
    weak_learners.append(tree)
    if fErrror<0.4:
        break
pyplot.scatter(data[:,0],data[:,1],s=3)
pyplot.scatter(data[:,0],fres,s=3,c="red")
pyplot.show()
